package com.atguigui.leetcode;

import java.util.HashMap;

/**
 * 1781.所有子字符串美丽值之和
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/12/12 9:13
 */
public class P1781SumOfBeautyOfAllSubstrings {
    public static void main(String[] args) {
        Solution solution = new P1781SumOfBeautyOfAllSubstrings().new Solution();
        // TO TEST
    }

    class Solution {
        public int beautySum(String s) {
            int res = 0;
            HashMap<String, Integer> map = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                //存储26个字母，并计算出现次数
                int[] cnt = new int[26];
                int maxFreq = 0;
                for (int j = i; j < s.length(); j++) {
                    //最大的
                    cnt[s.charAt(j) - 'a']++;
                    maxFreq = Math.max(maxFreq, cnt[s.charAt(j) - 'a']);
                    int minFreq = s.length();
                    //找出最小的
                    for (int k = 0; k < 26; k++) {
                        if (cnt[k] > 0) {
                            minFreq = Math.min(minFreq, cnt[k]);
                        }
                    }
                    res += maxFreq - minFreq;
                }

            }
            return res;
        }
    }
}
